package org.example.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liyishan
 * @date 2023/10/7 10:40
 * @apiNote
 */

public class Test00216CombinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(1,9,k,n,res,list);
        return res;
    }
    public static void dfs(int start,int end,int k,int sum,List<List<Integer>> res,List<Integer> list){
        if(list.size() >k || list.size() +(end - start + 1) < k ){
            return;
        }
        if(list.size() == k){
            int tempSum = 0;
            for(int num:list){
                tempSum+=num;
            }
            if(tempSum == sum){
                res.add(new ArrayList<>(list));
                return;
            }
        }
        list.add(start);
        dfs(start+1,end,k,sum,res,list);
        list.remove(list.size() - 1);
        dfs(start+1,end,k,sum,res,list);

    }

    public static void dfs2(int start,int end,int k,int sum,List<List<Integer>> res,List<Integer> list){
        if(list.size() > k){
            return;
        }
        if(sum == 0 && list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i<=end;i++){
            if(sum - i <0){
                break;
            }
            list.add(i);
            dfs2(i+1,end,k,sum-i,res,list);
            list.remove(list.size()-1);
        }
    }




}
